package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC347 {
    public long startExecuteTime = System.currentTimeMillis();


    public int[] topKFrequent_Passed_01(int[] arr, int k) {
        Map<Integer, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {
                map.put(arr[i], map.get(arr[i]) + 1);
            } else {
                map.put(arr[i], 1);
            }
        }

        Map<Integer, Integer> sortedMap = sortByValue(map);
        List<Integer> res = new ArrayList<>();
        int count = 1;
        for (Map.Entry<Integer, Integer> entry : sortedMap.entrySet()) {
            if (count++ <= k) {
                res.add(entry.getKey());
            }
        }

        int[] resArray = new int[res.size()];
        int i = 0;
        for (Integer re : res) {
            resArray[i++] = re;
        }

        return resArray;
    }

    public <K, V extends Comparable<? super V>> Map<K, V> sortByValue(Map<K, V> map) {
        Map<K, V> result = new LinkedHashMap<>();

        map.entrySet().stream()
                .sorted(Map.Entry.<K, V>comparingByValue()
                        .reversed()).forEachOrdered(e -> result.put(e.getKey(), e.getValue()));
        return result;
    }


    public int[] topKFrequent(int[] arr, int k) {
        Map<Integer, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {
                map.put(arr[i], map.get(arr[i]) + 1);
            } else {
                map.put(arr[i], 1);
            }
        }

        List<Integer>[] frequency = new List[arr.length + 1];
        for (int key : map.keySet()) {
            int frequencyIndex = map.get(key);
            if (frequency[frequencyIndex] == null) {
                frequency[frequencyIndex] = new ArrayList<>();
            }
            frequency[frequencyIndex].add(key);
        }

        // reverse order
        List<Integer> res = new ArrayList<>();
        for (int i = frequency.length - 1; i >= 0 && res.size() < k; i--) {
            if (frequency[i] == null) continue;
            res.addAll(frequency[i]);
        }

        int[] resArray = new int[res.size()];
        int i = 0;
        for (Integer re : res) {
            resArray[i++] = re;
        }

        return resArray;
    }


    public static void main(String[] args) throws Exception {
        LC347 an = new LC347();
        int[] arr = InputUtil.toIntegerArray("[4,1,-1,2,-1,2,3]");
        System.out.println(an.topKFrequent(arr, 2));


        System.out.println("\nanswer total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
